package com.zhang.tree;

import com.sun.org.apache.xerces.internal.impl.dv.xs.TypeValidator;

/**
 * 二叉树
 */
public class BinaryTree<T extends Comparable<T>> {

     class TreeNode<T extends Comparable<T>>{
        private T value;
        private TreeNode<T> left;
        private TreeNode<T> right;
        private TreeNode<T> parent;

        TreeNode(T value)
        {
            this(value,null,null,null);
        }
        TreeNode(T value,TreeNode left,TreeNode right,TreeNode parent)
        {
            this.value=value;
            this.left=left;
            this.right=right;
            this.parent=parent;
        }
    }
    private TreeNode<T> root;
    BinaryTree()
    {
        root=null;
    }


    //遍历树
    public void preOrder(String f) {

        switch (f)
        {
            case "前":
                preOrder(root);  System.out.println();
                break;
            case "中":
                inOrder(root);System.out.println();
                break;
            case "后":
                postOrder(root);  System.out.println();
                break;
        }
    }
    //前序遍历
    private void preOrder(TreeNode<T> tree) {
        if(tree != null) {
            System.out.print(tree.value+" ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }
    //中序遍历
    private void inOrder(TreeNode<T> tree) {
        if(tree != null) {
            inOrder(tree.left);
            System.out.print(tree.value+" ");
            inOrder(tree.right);
        }
    }
    //后续遍历
    private void postOrder(TreeNode<T> tree) {
        if(tree != null)
        {
            postOrder(tree.left);
            postOrder(tree.right);
            System.out.print(tree.value+" ");
        }
    }

    /**
     * (递归实现)查找"二叉树x"中键值为key的节点
     */
    public TreeNode<T> search(T key) {
         //递归
        return search(root, key);
        // 循环   return    iterativeSearch(root,key);
    }
    private TreeNode<T> search(TreeNode<T> x, T key) {
        if (x==null)
            return x;

        int cmp = key.compareTo(x.value);
        if (cmp < 0)
            return search(x.left, key);
        else if (cmp > 0)
            return search(x.right, key);
        else
            return x;
    }
    /**
     * (非递归实现)查找"二叉树x"中键值为key的节点
     */
    private TreeNode<T> iterativeSearch(TreeNode<T> x, T key) {
        while (x != null) {
            int cmp = key.compareTo(x.value);

            if (cmp < 0)
                x = x.left;
            else if (cmp > 0)
                x = x.right;
            else
                return x;
        }

        return x;
    }
    /**
         * 查找最大值,就是一直往右找找到最右边的值
         */
    private TreeNode<T> maximum(TreeNode<T> tree) {
        if (tree == null)
            return null;

        while(tree.right != null)
            tree = tree.right;
        return tree;
    }

    public T maximum() {
            TreeNode<T> p = maximum(root);
        if (p != null)
            return p.value;

        return null;
    }

    /**
     * 查找最小节点
     * @param tree
     * @return
     */
    private TreeNode<T> minimum(TreeNode<T> tree) {
        if (tree == null)
            return null;

        while(tree.left != null)
            tree = tree.left;
        return tree;
    }

    public T minimum() {
        TreeNode<T> p = minimum(root);
        if (p != null)
            return p.value;

        return null;
    }

    /**
     * 新建结点(key)，并将其插入到二叉树中
     *
     * 参数说明:
     *     tree 二叉树的根结点
     *     key 插入结点的键值
     */
    public void insert(T key) {
        TreeNode<T> z=new TreeNode<T>(key,null,null,null);
        // 如果新建结点失败，则返回。
        if (z != null)
            insert(this, z);
    }
    /**
     * 将结点插入到二叉树中
     *
     * 参数说明:
     *     tree 二叉树的
     *     z 插入的结点
     */
    private void insert(BinaryTree<T> bst, TreeNode<T> z) {
        int cmp;
        TreeNode<T> y = null;
        TreeNode<T> x = bst.root; // 8

        // 查找z的插入位置
        while (x != null) {
            y = x;   // y=8 y=4 y=2
            cmp = z.value.compareTo(x.value); //-1
            if (cmp < 0)
                x = x.left;    //x=4 x=2 x=null
            else
                x = x.right;
        }

        z.parent = y;   //2
        if (y==null)
            bst.root = z; // 1
        else {
            cmp = z.value.compareTo(y.value);
            if (cmp < 0)
                y.left = z;
            else
                y.right = z;
        }
    }





    public  void show(){
           TreeNode treeNode=new TreeNode(8);
              treeNode.left=new TreeNode(4);
            treeNode.left.left=new TreeNode(2);
              treeNode.right=new TreeNode(12);
            treeNode.right.right=new TreeNode(16);
            BinaryTree binaryTree=new BinaryTree();
            binaryTree.root=  treeNode;
            binaryTree.insert(1);
            binaryTree.preOrder("前");
            binaryTree.preOrder("中");
            binaryTree.preOrder("后");
//            System.out.println("查找‘前’:"+binaryTree.search("前"));
//            System.out.println("查找'左':"+binaryTree.search("左").value);
            System.out.println("查找最大值："+binaryTree.maximum());
            System.out.println("查找最小值："+binaryTree.minimum());

        }
}

class Tests{
    public static void main(String[] arg0){
        BinaryTree binaryTree=new BinaryTree();
        binaryTree.show();

    }
        }


